Improved Animal Tracking Algorithm using Distributed Kalman Filter-based Algortihms

Animal tracking has been addressed by different initiatives over the last two decades. Most of them rely on satellite connectivity on every single node and lack of energy-saving strategies. This paper presents several new contributions on the tracking of dynamic heterogeneous asynchronous networks (primary nodes with GPS and secondary nodes with a kinetic generator) motivated by the animal tracking paradigm with random transmissions. A simple approach based on connectivity and coverage intersection is compared with more sophisticated algorithms based on ad-hoc implementations of distributed Kalman-based filters that integrate measurement information using Consensus principles in order to provide enhanced accuracy. Several simulations varying the coverage range, the random behavior of the kinetic generator (modeled as a Poisson Process) and the periodic activation of GPS are included. In addition, this study is enhanced with HW developments and implementations on commercial off-the-shelf equipment which show the feasibility for performing these proposals on real hardware.

An improved bit parallel exact maximum clique algorithm

This paper describes new improvements for BB-MaxClique (San Segundo et al. in Comput Oper Resour 38(2):571–581, 2011 ), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, pp 191–203, 2010 ), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB-MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.

Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

Sequential origin in the high performance properties of spider dragline silk

Major ampullate (MA) dragline silk supports spider orb webs, combining strength and extensibility in the toughest biomaterial. MA silk evolved ~376 MYA and identifying how evolutionary changes in proteins influenced silk mechanics is crucial for biomimetics, but is hindered by high spinning plasticity. We use supercontraction to remove that variation and characterize MA silk across the spider phylogeny. We show that mechanical performance is conserved within, but divergent among, major lineages, evolving in correlation with discrete changes in proteins. Early MA silk tensile strength improved rapidly with the origin of GGX amino acid motifs and increased repetitiveness. Tensile strength then maximized in basal entelegyne spiders, ~230 MYA. Toughness subsequently improved through increased extensibility within orb spiders, coupled with the origin of a novel protein (MaSp2). Key changes in MA silk proteins therefore correlate with the sequential evolution high performance orb spider silk and could aid design of biomimetic fibers.

Error estimation for the linearized auto-localization algorithm

The Linearized Auto-Localization (LAL) algorithm estimates the position of beacon nodes in Local Positioning Systems (LPSs), using only the distance measurements to a mobile node whose position is also unknown. The LAL algorithm calculates the inter-beacon distances, used for the estimation of the beacons’ positions, from the linearized trilateration equations. In this paper we propose a method to estimate the propagation of the errors of the inter-beacon distances obtained with the LAL algorithm, based on a first order Taylor approximation of the equations. Since the method depends on such approximation, a confidence parameter τ is defined to measure the reliability of the estimated error. Field evaluations showed that by applying this information to an improved weighted-based auto-localization algorithm (WLAL), the standard deviation of the inter-beacon distances can be improved by more than 30% on average with respect to the original LAL method.

An algorithm for controllability in complex networks

In this paper structural controllability of complex networks is anyzed. A new algorithm is proposed which constructs a structural control scheme for a given network by avoiding the absence of dilations and by guaranteeing the accessibility of all nodes. Such accessibility is solved via a wiring procedure; this procedure, based on determining the non-accessible regions of the network, has been improved in this new proposed algorithm. This way, the number of dedicated controllers is reduced with respect to the one provided by previous existing algorithms.

Simulating improved combinations tillage-rotation under dryland conditions.

Crop simulation models allow analyzing various tillage-rotation combinations and exploring management scenarios. This study was conducted to test the DSSAT (Decision Support System for Agrotechnology Transfer) modelling system in rainfed semiarid central Spain. The focus is on the combined effect of tillage system and winter cereal-based rotations (cereal/legume/fallow) on the crop yield and soil quality. The observed data come from a 16-year field experiment. The CERES and CROPGRO models, included in DSSAT v4.5, were used to simulate crop growth and yield, and DSSAT- CENTURY was used in the soil organic carbon (SOC) and soil nitrogen (SN) simulations. Genetic coefficients were calibrated using part of the observed data. Field observations showed that barley grain yield was lower for continuous cereal (BB) than for vetch (VB) and fallow (FB) rotations for both tillage systems. The CERES-Barley model also reflected this trend. The model predicted higher yield in the conventional tillage (CT) than in the no tillage (NT) probably due to the higher nitrogen availability in the CT, shown in the simulations. The SOC and SN in the top layer only, were higher in NT than in CT, and decreased with depth in both simulated and observed values. These results suggest that CT-VB and CT-FB were the best combinations for the dry land conditions studied. However, CT presented lower SN and SOC content than NT. This study shows how models can be a useful tool for assessing and predicting crop growth and yield, under different management systems and under specific edapho-climatic conditions. Additional key words: CENTURY model; CERES-Barley; crop simulation models; DSSAT; sequential simula- tion; soil organic carbon.